Section: New Results

Optimization

Nonsmooth analysis and optimization on matrix manifolds

Participant : Jérôme Malick.

Optimization on matrix manifolds is an emerging fields of research in optimization, driven by applications in robotics. We have contributed on two different projects.

• Numerical efficiency of optimization methods. Newton method on manifolds would require to compute a geodiesic (that is to solve a ODE). It is clear that replacing classical differential-geometric objects with certain approximations, resulting in faster and possibly more robust algorithms. With our colleague P.-A. Absil from the Department of Mathematical Engineering of the Ecole Polytechnique de Louvain (Belgique), we propose in [16] a way to construct “retractions” (a key step when applying optimization algorithms on matrix manifolds) by projecting onto the submanifold. We show that the operation remains a retraction if the projection is generalized to a projection-like procedure that consists of coming back to the submanifold along “admissible” directions. This theory offers a framework in which previously-proposed retractions can be analyzed, as well as a toolbox for constructing new ones. Illustrations are given for projection-like procedures on some specific manifolds for which we have an explicit, easy-to-compute expression.

• Towards the application of matrix optimization techniques to spectral manifolds. Spectral sets are sets of matrices that depend only on the constraints on the eigenvalues: $S$ is a spectral set if $S={\lambda }^{-1}\left(C\right)$ with $C$ a subset of ${ℝ}^n$. A spectral set $S$ inherits from properties of the underlying set $C$, such as convexity. We prove in [46] that the spectral sets associated to smooth manifolds in ${ℝ}^n$ (having some local symmetry) are themselves manifolds in the space of matrices. This result looks simple but generalizes several useful particular cases, and was extremely difficult to prove: we brace together tools from nonsmooth analysis, differential geometry, group theory and spectral analysis.

Semidefinite programming and combinatorial optimization

Participants : Nathan Krislock, Jérôme Malick.

We have worked with Frederic Roupin (Prof. at Paris XIII) on the use of semidefinite programming to solve combinatorial optimization problems to optimality. Within exact resolution schemes (branch-and-bound), “good” bounds are those with a “good” balance between tightness and computing times.

We proposed a new family of semidefinite bounds for 0-1 quadratic problems with linear or quadratic constraints [26] , [54] . An interesting feature is that the final accuracy level is controlled by real parameter acting like a cursor. This gives ways to trade computing time for a (small) deterioration of the quality of the usual semidefinite bounds, in view of enhancing this efficiency in exact resolution schemes. Extensive numerical comparisons et tests showed the superior quality of our bounds on standard test-problems (unconstrained 0-1 quadratic problems, heaviest k-subgraph problems, and graph bisection problems).

We have embedded the new bounds within branch-and-bound algorithms to solve 2 standard combinatorial optimization problems to optimality.

• Heaviest k-subgraph problems. Our algorithm [26] takes advantage of the new bounds to prune very well in the search tree. Its performances are then comparable with the best method (based on convex quadratic relaxation using CPLEX as an engine). In practice, our method works particularly fine on the most difficult instances (with a large number of vertices, small density and small k).

• Max-cut. We are working on extending our algorithm to max-cut problems [53] . It dynamically manages polyedral and semidefinite relaxations to outperform the state-of-the-art solver ( [56] ) on the large test-problems.

Marginal prices in electricity production

Participants : Claude Lemaréchal, Jérôme Malick, Welington Oliveira, Sofia Zaourar.

Two subjects were involved this year in our ongoing collaboration with EdF.

• Stabilizing prices. Unit-commitment optimization problems in electricity production are large-scale, nonconvex and heterogeneous, but they are decomposable by Lagrangian duality. Realistic modeling of technical production constraints makes the dual objective function computed inexactly though. An inexact version of the bundle method has been dedicated to tackle this difficulty [52] . However, the computed optimal dual variables show a noisy and unstable behaviour, that could prevent their use as price indicator. We propose a simple and controllable way to stabilize the dual optimal solutions, by penalizing the total variation of the prices [59] . Our illustrations on the daily electricity production optimization of EDF show a strinking stabilization at a negligible cost.

• Accelerating the solution phase by the so-called disaggregation technique [49] , using the fact that (see Activity Report of 2010) the dual objective function is the sum of two terms: one coming from primal cost, one coming from valorization of constraints (plus possibly a third term when price stabilization is present). The resulting CPU time is drastically improved, sometimes divided by 10.